// Quadtree lying x-z plane.

#pragma once

#include "Vector3.h"
#include "GlutStuff.h"
#include <vector>

typedef struct { 

	int* particle_index;
	int particle_num;

} Particle;


class QuadTree {

	enum {
		X_AXIS = 0,
		Y_AXIS = 1,
		Z_AXIS = 2
	};

private:

	static struct _particle {
		Vector3* pos;
		Vector3* vel;
		Vector3* mm;
	} particle;

	static int max_particle;

	Particle m_particles;

	bool m_hasChild;

	Vector3 m_centerPos;
	
	Vector3 m_startPos;
	Vector3 m_endPos;

	
	QuadTree* m_parent;				//parent node
	QuadTree* m_child[4];			//child node
	
	int m_depth;					

public:

	QuadTree() {
		m_particles.particle_num = 0;
		m_particles.particle_index = NULL;

		m_parent = NULL;

		m_depth = 0;
		m_hasChild = false;
	};

	~QuadTree() {

	}

	inline void SetBoundingBox(Vector3& startPos, Vector3& endPos) {
		m_startPos = startPos;
		m_endPos = endPos;

		m_centerPos = (m_startPos + m_endPos) * 0.5f;

	};

	static void SetParticleArray(Vector3* pos, Vector3* vel, Vector3* mm) {
		particle.pos = pos;
		particle.vel = vel;
		particle.mm = mm;
	};

	void CreateIndexList(int num) {
		m_particles.particle_index = new int[num];
		for (int i=0; i<num; i++) {
			m_particles.particle_index[i] = i;
		}
		m_particles.particle_num = num;
	}

	void DeleteIndexList() {
		if (m_particles.particle_index)
		delete[] m_particles.particle_index;
	}

	void DeleteAll() {
		if (m_hasChild) {
			for (int i=0; i<4; i++) {
				m_child[i]->DeleteAll();
				delete m_child[i];
				m_hasChild = false;
			}
		}
	}

	void SubDivide();

	void IncreaseDepth() {
		m_depth++;
		if (m_parent)
			m_parent->IncreaseDepth();			
	}

	int SortIndex(int* indexlist, int num, int axis);

	__forceinline Vector3 GetPtcPos(int idx) {
		return particle.pos[m_particles.particle_index[idx]];
	}

	QuadTree* FindNode(Vector3& pos);



	void FindDepthCallBack(int depth, void(*callback)(QuadTree*));


	static Vector3 GetPosition(QuadTree* qt) {
		return qt->m_centerPos;
	}

	static void DrawPointAtCenter(QuadTree* qt) {
		if (!qt->m_particles.particle_num) return;
		glColor3f(0.9, 0.1, 0.0);
		glBegin(GL_POINTS);
		glVertex3f(qt->m_centerPos.x(), 0.1f, qt->m_centerPos.z());
		glEnd();
	}

	void DrawLine();
};


